package com.learn.finished;
/*

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

 */

public class num_441 {
    public static int arrangeCoins(int n) {
        //转换成数学问题的话，其实就是求小于n的最大数量
        for (int i = 1; i <= n; i++) {
            n = n - i;
            if (n <= i) {
                return i;
            }
        }
        return 0;
    }

    public static int arrangeCoins3(int n) {
        long low = 1, high = n;
        while (low < high) {
            long mid = low + high + 1 >> 1;
            long cost = mid * (mid + 1) / 2;
            if (cost <= n) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return (int) high;
    }

    //二分法
    public static int arrangeCoins1(int n) {
        int low = 0, high = n;
        while (low <= high) {
            int mid = (low + high) / 2;
            //出现平方，可以考虑牛顿迭代
            int cost = mid * (mid + 1) / 2;
            if (cost == n) {
                return mid;
            } else if (cost > n) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    public static int arrangeCoins2(int n) {
        if (n == 0) {
            return 0;
        }
        return (int) sqrt(n, n);
    }

    private static double sqrt(double x, int n) {
        double res = (x + (2 * n - x) / x) / 2;
        if (res == x) {
            return x;
        } else {
            return sqrt(res, n);
        }
    }
}
